package LinkList;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: DoublePointer
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-18  20:19
 * @Description: TODO
 * @Version: 1.0
 */
public class 排序链表148 {

    // node的定义
    class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    // 快慢指针 ，然后采用双链表合并排序
    // 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
    // 对两个子链表分别排序。
    // 将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        // 终止递归程序
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode mid = midnode(head, tail);
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    public ListNode midnode(ListNode head,ListNode tail){
        ListNode slow = head;
        ListNode fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        // 发现中间node 分割成为两个链表来实现
        return slow;
    }

    // 链表合并
    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead;
        ListNode temp1 = head1;
        ListNode temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}
